#include <stdio.h>
#include <stdlib.h>

#include "treeUtils.h"

/*
*  1. DFS添加节点，如果为空，则申请节点添加。如果不为空，则跟root节点比较，
*     小于的添加左节点，否则添加右节点
*/

struct TreeNode *AddNode(struct TreeNode *root, int data) {
    if (root == NULL) {
        root = calloc(1, sizeof(struct TreeNode));
        if (!root) {
            return NULL;
        }
        root->val = data;
    } else if (root->val > data) {
        root->left = AddNode(root->left, data);
    } else {
        root->right = AddNode(root->right, data);
    }
    return root;
}

struct TreeNode *bstFromPreorder(int *preorder, int preorderSize) {
    if (preorderSize == 0) {
        return NULL;
    }
    struct TreeNode *root = NULL;
    for (int i = 0; i < preorderSize; ++i) {
        root = AddNode(root, preorder[i]);
    }
    return root;
}

int main() {
    setbuf(stdout, 0);
    int test[6] = {8, 5, 1, 7, 10, 12};
    struct TreeNode *root = bstFromPreorder(test, 6);

    struct TreeNode *tmp[100] = {0};
    tmp[0] = root;
    int count = 1;
    int start = 0;
    printf(" ret: %d ", tmp[start]->val);
    while (start < count) {
        int end = count;
        for (; start < end; ++start) {
            if (tmp[start]->left) {
                tmp[count++] = tmp[start]->left;
                printf(" %d ", tmp[start]->left->val);
            }
            if (tmp[start]->right) {
                tmp[count++] = tmp[start]->right;
                printf("%d ", tmp[start]->right->val);
            }
        }
        start = end;
    }
}

